import kotlin.math.max
import kotlin.math.min

//两数之和
fun twoSum(nums: IntArray, target: Int): IntArray {
    val resultValuePair = mutableMapOf<Int, Int>()
    for (index in 0..<nums.size) {
        val value = target - nums[index]
        val valuePair = resultValuePair[value]
        if (valuePair != null) {
            return intArrayOf(index, valuePair)
        } else {
            resultValuePair[nums[index]] = index
        }
    }
    return intArrayOf()
}

//49. 字母异位词分组
fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val resultMap = mutableMapOf<Int, MutableList<String>>()
    strs.forEach { str ->
        val mapChars = mutableMapOf<Char, Int>()
        str.forEach { char ->
            val tmp = mapChars.getOrDefault(char, 0)
            mapChars[char] = tmp + 1
        }
        val strBuilder = StringBuilder()
        for (char in 'a'..'z') {
            strBuilder.append(char)
            strBuilder.append(mapChars.getOrDefault(char, 0))
        }
        val tmpList = resultMap.getOrPut(strBuilder.toString().hashCode()) { mutableListOf() }
        tmpList.add(str)
    }
    return resultMap.map { it.value }
}

//128. 最长连续序列
fun longestConsecutive(nums: IntArray): Int {
    val numSet = mutableSetOf<Int>()
    nums.forEach {
        numSet.add(it)
    }
    var longestStreak = 0
    numSet.forEach { value ->
        if (!numSet.contains(value - 1)) {
            var tmpStreak = 1
            var currentValue = value
            while (numSet.contains(currentValue + 1)) {
                currentValue++
                tmpStreak++
            }
            longestStreak = max(longestStreak, tmpStreak)
        }
    }
    return longestStreak
}

//283. 移动零
fun moveZeroes(nums: IntArray): Unit {
    var i = 0
    nums.forEach {
        if (it != 0) {
            nums[i] = it
            i++
        }
    }
    for (index in i..<nums.size) {
        nums[index] = 0
    }
}

//11. 盛最多水的容器
fun maxArea(height: IntArray): Int {
    var maxArea = 0
    var start = 0
    var end = height.size - 1
    while (start < end) {
        val areaHeight = min(height[start], height[end])
        maxArea = max(maxArea, (end - start) * areaHeight)
        if (height[start] <= height[end]) {
            start--
        } else {
            end--
        }
    }
    return maxArea
}

//15. 三数之和
fun threeSum(nums: IntArray): List<List<Int>> {
    val target = 0
    nums.sort()
    val result = mutableListOf<List<Int>>()
    for (first in nums.indices) {
        if (first > 0 && nums[first] == nums[first - 1]) continue
        var leftIndex = first + 1
        var rightIndex = nums.size - 1
        val currentNumber = nums[first]
        while (leftIndex < rightIndex) {
            val leftNumber = nums[leftIndex]
            val rightNumber = nums[rightIndex]
            val sum = leftNumber + rightNumber + currentNumber
            if (target == sum) {
                result.add(listOf(currentNumber, rightNumber, leftNumber))
                while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
                    leftIndex++
                }
                while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
                    rightIndex--
                }
                leftIndex++
                rightIndex--
            } else if (sum < target) {
                leftIndex++
            } else {
                rightIndex--
            }
        }
    }
    return result
}

// 3. 无重复字符的最长子串
fun lengthOfLongestSubstring(s: String): Int {
    var left = 0
    var right = 0
    val setChar = mutableSetOf<Char>()
    var res = 0
    while (right < s.length) {
        val tmpChar = s[right]
        if (setChar.contains(tmpChar)) {
            res = max(res, right - left)
            setChar.remove(s[left])
            left++
        } else {
            setChar.add(tmpChar)
            right++
        }
    }
    return max(res, right - left)
}

//438. 找到字符串中所有字母异位词
fun findAnagrams(s: String, p: String): List<Int> {
    if (p.length > s.length) return emptyList()
    val sArray = IntArray(26)
    val pArray = IntArray(26)
    val result = mutableListOf<Int>()
    for (index in 0..p.length - 1) {
        sArray[s[index] - 'a']++
        pArray[p[index] - 'a']++
    }
    if (pArray.contentEquals(sArray)) {
        result.add(0)
    }
    for (index in 0..s.length - p.length - 1) {
        sArray[s[index] - 'a']--
        sArray[s[index + p.length] - 'a']++
        if (pArray.contentEquals(sArray)) {
            result.add(1 + index)
        }
    }
    return result
}

fun subarraySum(nums: IntArray, k: Int): Int {
    val mapPreSums = mutableMapOf<Int, Int>()
    mapPreSums[0] = 1
    var preSum = 0
    var count = 0
    for (index in 0..<nums.size) {
        preSum += nums[index]
        val tmp = mapPreSums[preSum - k]
        if (tmp != null) {
            count += tmp
        }
        mapPreSums[preSum] = mapPreSums.getOrDefault(preSum, 0) + 1
    }
    return count
}

//53. 最大子数组和
// 假设 f(x) 表示 前x项的最大和 那么就有 f(x) = max(f(x -1) + nums[x]  , nums[x] )
fun maxSubArray(nums: IntArray): Int {
    var maxResult = nums[0]
    var pre = nums[0]
    for (index in 1..<nums.size) {
        pre = max(pre + nums[index], nums[index])
        maxResult = max(maxResult, pre)
    }
    return maxResult
}

// 56. 合并区间
fun merge(intervals: Array<IntArray>): Array<IntArray> {
    val result = mutableListOf<IntArray>()
    intervals.sortBy { it[0] }
    intervals.forEach {
        val left = it[0]
        val right = it[1]
        if (result.size == 0) {
            result.add(intArrayOf(left, right))
        } else {
            val lastArray = result[result.size - 1]
            if (left > lastArray[1]) {
                result.add(intArrayOf(left, right))
            } else {
                lastArray[1] = max(lastArray[1], right)
            }
        }
    }
    return result.toTypedArray()
}

//238. 除自身以外数组的乘积
fun productExceptSelf(nums: IntArray): IntArray {
    val leftArray = IntArray(nums.size)
    val rightArray = IntArray(nums.size)
    leftArray[0] = 1
    for (index in 1..<nums.size) {
        leftArray[index] = leftArray[index - 1] * nums[index - 1]
    }
    rightArray[nums.size - 1] = 1
    for (index in nums.size - 2 downTo 0) {
        rightArray[index] = rightArray[index + 1] * nums[index + 1]
    }
    val result = IntArray(nums.size)
    for (index in 0..nums.size - 1) {
        result[index] = rightArray[index] * leftArray[index]
    }
    return result
}

//41. 缺失的第一个正数 4 3 2 1
fun firstMissingPositive(nums: IntArray): Int {
    for (index in 0..nums.size - 1) {
        while (nums[index] > 0 && nums[index] - 1 < nums.size && nums[index] != nums[nums[index] - 1]) {
            val tmp = nums[index]
            nums[index] = nums[tmp - 1]
            nums[tmp - 1] = tmp
        }
    }
    var len = 0
    for (index in 0..nums.size - 1) {
        if (nums[index] - 1 != index) {
            return index + 1
        }
        len++
    }
    return len + 1
}

fun main() {
    println(firstMissingPositive(intArrayOf(1, 1)))
}